﻿#include <stdlib.h>

#define MaxSize 10

/*
图的最小生成树（最小代价树），带权连通图的权值之和最小的生成树
注意：1.连通图本身是一棵树，最小生成树是本身。2.只有连通图才有生成树，非连通图只有生成森林
*/
typedef struct VertexType {
	int no;
	char info;
}VertexType;

typedef struct Mgraph {
	int n, e;
	int edges[MaxSize][MaxSize];
	VertexType vex[MaxSize];
}Mgraph;


//prim算法：每次选择最小代价的结点加入生成树。时间复杂度O(|V|²)，适用于边稠密图
void prim(Mgraph G,int v,int &sum) {
	int vset[MaxSize], lowcost[MaxSize];//定义vset存储已并入生成树的结点；lowcost存放当前生成树到剩余各顶点的最短边的权值（最小权值）
	//初始化
	sum = 0;
	for (int i = 0; i < G.n; i++)
	{
		vset[i] = 0;
		lowcost[i] = G.edges[v][i];
	}
	vset[v] = 1;//添加顶点v
	//循环查找下一个顶点
	int min,k;//记录当前选择的顶点以及最小代价
	for (int i = 0; i < G.n-1; i++)
	{
		min = INT_MAX;
		for (int j = 0; j < G.n; j++)
		{
			if (vset[j] == 0 && lowcost[j] < min) {
				min = lowcost[j];
				k = j;
			}
		}
		vset[k] = 1;//并入生成树
		sum += min;
		//更新权值lowcost
		for (int j = 0; j < G.n; j++)
		{
			if (vset[j] == 0 && G.edges[k][j] < lowcost[j]) {
				lowcost[j] = G.edges[k][j];
			}
		}
	}

}



//kruskal算法：每次选择权值最小的边，使边两头连通（已连通的不选），直到所有结点连通。时间复杂度O(|E|log2|E|),适用于边稀疏图
typedef struct Road {
	int a, b;//边连接的端点
	int w;//权值
}Road;//定义边

Road road[MaxSize];
int tree[MaxSize];//并查集数组

//在并查集数组中，查询顶点a的祖宗结点
int getRoot(int a) {
	/*while (tree[a] != a) {
		a = tree[a];
	}*/
	if (tree[a] = a) {
		return a;
	}
	else {
		//return getRoot(tree[a]);
		tree[a] = getRoot(tree[a]);//这里路径压缩，记录a的根结点
	}
	return tree[a];
}

void kruskal(Mgraph G,Road road[],int &sum) {
	//初始化
	sum = 0;
	for (int i = 0; i < G.n; i++)
	{
		tree[i] = i;
	}
	//对数组中的边按照权值递增排序（可采取不同的排序算法）
	Sort(road, G.e);

	int a, b;//当前处理的顶点的祖宗
	for (int i = 0; i < G.e; i++)
	{
		//对边的顶点集合，进行合并
		a = getRoot(road[i].a);
		b = getRoot(road[i].b);
		//一条边的两个顶点，对应的根结点a,b若相等，说明两个顶点都已经加入了生成树
		if (a != b) {
			tree[a] = b;
			sum += road[i].w;
		}
	}
}